home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / prio / _p_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  11.3 KB  |  443 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _p_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/p_heap.h>
  17.  
  18.  
  19. static p_heap const *class_ptr;
  20.  
  21. // ============== comparison_link Macros (s.n.) ================================
  22.  
  23. #define comparison_link(with_el,new_el)\
  24.   if (cmp(with_el->key,new_el->key)<0)\
  25.     { with_el->r_child=new_el->r_child;\
  26.       if (with_el->r_child!=nil)\
  27.               with_el->r_child->parent=with_el;\
  28.       new_el->r_child=with_el->l_child;\
  29.       if (new_el->r_child!=nil)\
  30.               new_el->r_child->parent=new_el;\
  31.       new_el->parent=with_el;  \
  32.       with_el->l_child=new_el; }\
  33.   else\
  34.     { with_el->r_child=new_el->l_child;\
  35.       if (with_el->r_child!=nil)\
  36.               with_el->r_child->parent=with_el;\
  37.       new_el->parent=with_el->parent;\
  38.       if (new_el->parent!=nil)\
  39.               new_el->parent->r_child=new_el; \
  40.       new_el->l_child=with_el;\
  41.       with_el->parent=new_el;\
  42.       with_el = new_el; }
  43.  
  44. #define int_comparison_link(with_el,new_el)\
  45.   if (with_el->key < new_el->key)\
  46.     { with_el->r_child=new_el->r_child;\
  47.       if (with_el->r_child!=nil)\
  48.               with_el->r_child->parent=with_el;\
  49.       new_el->r_child=with_el->l_child;\
  50.       if (new_el->r_child!=nil)\
  51.               new_el->r_child->parent=new_el;\
  52.       new_el->parent=with_el;  \
  53.       with_el->l_child=new_el; }\
  54.   else\
  55.     { with_el->r_child=new_el->l_child;\
  56.       if (with_el->r_child!=nil)\
  57.               with_el->r_child->parent=with_el;\
  58.       new_el->parent=with_el->parent;\
  59.       if (new_el->parent!=nil)\
  60.               new_el->parent->r_child=new_el; \
  61.       new_el->l_child=with_el;\
  62.       with_el->parent=new_el;\
  63.       with_el = new_el; }
  64.  
  65.  
  66.  
  67. //====== construct (p_heap&) ===========================================
  68.  
  69. p_heap::p_heap(const p_heap& with)
  70. {
  71.     item_count =0;
  72.     if((this!=&with)&&(with.item_count>0)){
  73.         class_ptr=&with;
  74.         copy_sub_tree(head,with.head);
  75.         class_ptr=this;
  76.     }
  77. }
  78.  
  79. //====== operator = =====================================================
  80.  
  81. p_heap& p_heap::operator=(const p_heap& with)
  82. {
  83.       if(this!=&with){
  84.          if((with.item_count>0)&&(item_count>0))
  85.                 clear();
  86.         class_ptr=&with;
  87.         copy_sub_tree(head,with.head);
  88.         class_ptr=this;
  89.                 
  90.         }
  91.         return(*this);
  92. }
  93.  
  94. //=========== copy_sub_tree =============================================
  95.  
  96. void  p_heap::copy_sub_tree(ph_item* whereto,ph_item* from) 
  97. {
  98.    if (item_count==0)   // target tree is empty 
  99.    {
  100.         
  101.          head =new ph_item(from->key,from->inf);
  102.          class_ptr->copy_key(head->key);
  103.          class_ptr->copy_inf(head->inf);
  104.          item_count++;
  105.         
  106.          do_copy(head,from->l_child,true);
  107.    }
  108.  
  109.    else
  110.         
  111.                 if ((cmp(whereto->key,from->key)<=0)  // precondition:
  112.                         &&(whereto->l_child==nil))    // subelement <= parent
  113.                 
  114.                         do_copy(whereto,from,true);
  115.                         // true: that is left child from whereto        
  116. }
  117.  
  118.  
  119.  
  120. //====== do_copy ======================================================
  121.  
  122. void p_heap::do_copy(ph_item* father,ph_item* from,bool direction)
  123. {
  124. // direction : false=right true=left
  125.  
  126.         
  127.         ph_item* hilf=new_ph_item(from->key,from->inf);
  128.         
  129.         hilf->parent=father;
  130.         if (direction)
  131.                 father->l_child=hilf;
  132.         else
  133.                 father->r_child=hilf;
  134.  
  135.         if (from->l_child!=nil)
  136.                 do_copy(hilf,from->l_child,true);
  137.                 
  138.         if (from->r_child!=nil)
  139.                 do_copy(hilf,from->r_child,false);
  140. }
  141.  
  142. //===== new_ph_item =====================================================
  143.  
  144. ph_item* p_heap::new_ph_item(GenPtr key,GenPtr inf)
  145. {
  146.         ph_item* help=new ph_item(key,inf);
  147.  
  148.         copy_key(help->key);
  149.         copy_inf(help->inf);
  150.         help->parent=nil;
  151.         item_count++;
  152.  
  153.         return help;
  154. }
  155.  
  156.         
  157.                 
  158. // ========== clear ====================================================
  159.  
  160. void p_heap::clear()
  161. {
  162.   if (item_count>0)
  163.         clear_sub_tree(head);
  164.         
  165. }
  166.  
  167. // ======= clear_sub_tree ===============================================
  168.  
  169. void p_heap::clear_sub_tree(ph_item* sub)
  170. {
  171.         
  172.         if (sub->l_child!=nil)
  173.                 clear_sub_tree(sub->l_child);
  174.         if (sub->r_child!=nil)
  175.                 clear_sub_tree(sub->r_child);
  176.         if (sub->parent!=nil)
  177.                 if(sub->parent->l_child==sub)
  178.                         sub->parent->l_child=nil;
  179.                 else
  180.                         sub->parent->r_child=nil;
  181.  
  182.         clear_key(sub->key);
  183.         clear_inf(sub->inf);
  184.         delete(sub);
  185.         item_count--;
  186. }
  187.                 
  188.  
  189.  
  190. //======= insert =======================================================
  191.  
  192. ph_item* p_heap::insert(GenPtr key,GenPtr inf)
  193. {       
  194.         ph_item* help;
  195.  
  196.         help = new ph_item(key,inf);
  197.         copy_key(help->key);
  198.         copy_inf(help->inf);
  199.  
  200.         if (item_count==0)      // very first element
  201.           { item_count++;
  202.             head=help;
  203.             return help;
  204.            }
  205.         else                    // just another element
  206.           { item_count++;
  207.             comparison_link(head,help);
  208.             return help;
  209.            }
  210.  
  211.         
  212. }
  213.  
  214.  
  215. // ====== decrease_key ==================================================
  216.  
  217. void p_heap::decrease_key(ph_item* which,GenPtr key)
  218. {
  219.    register ph_item* help2=nil;
  220.    register ph_item* which_parent = which->parent;
  221.  
  222.    if (int_type())
  223.      if (key <= which->key)  // smaller or equal to the old element
  224.       { 
  225.         which->key=key;
  226.    
  227.         if (which!=head)         // which is not already minimum
  228.         { if (which->r_child!=nil)
  229.           { help2=which->r_child;
  230.             help2->parent=which_parent;
  231.             which->r_child=nil;
  232.            }
  233.    
  234.           if (which_parent->l_child==which)
  235.              which_parent->l_child=help2;
  236.           else                    
  237.              which_parent->r_child=help2;
  238.    
  239.           which->parent=nil;
  240.           int_comparison_link(head,which);
  241.          }
  242.       }
  243.      else /* error */;
  244.    else
  245.      if (cmp(key,which->key)<=0)  // smaller or equal to the old element
  246.       { 
  247.         clear_key(which->key);
  248.         which->key=key;
  249.         copy_key(which->key);
  250.    
  251.         if (which!=head)         // which is not already minimum
  252.         { if (which->r_child!=nil)
  253.           { help2=which->r_child;
  254.             help2->parent=which_parent;
  255.             which->r_child=nil;
  256.            }
  257.    
  258.           if (which_parent->l_child==which)
  259.              which_parent->l_child=help2;
  260.           else                    
  261.              which_parent->r_child=help2;
  262.    
  263.           which->parent=nil;
  264.           comparison_link(head,which);
  265.          }
  266.       }
  267.      else /* error */;
  268. }                       
  269.                 
  270.  
  271. //========= delete_min_multipass ()  (multipass algorithm) =============
  272.  
  273. void p_heap::delete_min_multipass()
  274. {
  275.  if (item_count==1)     // only one element in structure
  276.    {
  277.         clear_key(head->key);
  278.         clear_inf(head->inf);
  279.         delete head;
  280.         item_count=0;
  281.    }
  282.    else
  283.    {
  284.         head=head->l_child;
  285.         clear_key(head->parent->key);
  286.         clear_inf(head->parent->inf);
  287.         delete head->parent;    // delete min
  288.         head->parent=nil;
  289.         item_count--;
  290.         
  291.       if (head->r_child!=nil)   // there are two ore more consecutive elements
  292.         head=multipass(head);
  293.     
  294.   }// end else
  295.  
  296. }
  297.  
  298. //======== delete_min_twopass, (twopass algorithm) ============================
  299.  
  300. void p_heap::delete_min_twopass()
  301. {
  302.         
  303.    if (item_count==1)   // only one element in structure
  304.    {
  305.         clear_key(head->key);
  306.         clear_inf(head->inf);
  307.         delete head;
  308.         item_count=0;
  309.    }
  310.    else
  311.    {
  312.         head=head->l_child;
  313.         clear_key(head->parent->key);
  314.         clear_inf(head->parent->inf);
  315.         delete head->parent;    // delete min
  316.         head->parent=nil;
  317.         item_count--;
  318.         
  319.       if (head->r_child!=nil)   // there are two ore more consecutive elements
  320.       
  321.         head=twopass(head);
  322.         
  323.  
  324.       } // end else
  325. }
  326.  
  327.  
  328.  
  329. // ============== twopass ================================================              
  330.         
  331. ph_item*  p_heap::twopass(ph_item* head)
  332. {
  333.  //pass 1 : left to right comparison link (successive pairs of root nodes)
  334.  
  335.   register ph_item* help1,*help2;
  336.  
  337.   help1=head;
  338.   help2=head->r_child;
  339.   
  340.   if (int_type())
  341.         while (help2!=nil)               // there are 2 ore more elements left
  342.         { head=help1->r_child->r_child;   // use of head as a helper
  343.           int_comparison_link(help1,help2);
  344.                 
  345.           if (head!=nil)       // first case comp _link
  346.              if (head->r_child!=nil)
  347.                { // second case
  348.                  // now we have to more nodes to test
  349.                  help2=head->r_child;
  350.                  help1=head;
  351.                 }
  352.              else
  353.                help2=nil;
  354.            else
  355.              { head=help1;     // last element in list
  356.                help2=nil;
  357.               }
  358.           }
  359.    else
  360.         while (help2!=nil)
  361.         { head=help1->r_child->r_child;
  362.           comparison_link(help1,help2);
  363.                 
  364.           if (head!=nil)
  365.              if (head->r_child!=nil)
  366.                { help2=head->r_child;
  367.                  help1=head;
  368.                 }
  369.              else
  370.                help2=nil;
  371.            else
  372.              { head=help1;
  373.                help2=nil;
  374.               }
  375.          }
  376.  
  377.   //pass 2 : right to left comparison link (allways the two rightmost nodes)
  378.  
  379.         help1=head->parent;
  380.         help2=head;
  381.  
  382.    if (int_type())
  383.         while (help1!=nil)
  384.         { int_comparison_link(help1,help2);
  385.           head=help1;
  386.           help2=help1;
  387.           help1=help1->parent;
  388.          }
  389.     else
  390.         while (help1!=nil)
  391.         { comparison_link(help1,help2);
  392.           head=help1;
  393.           help2=help1;
  394.           help1=help1->parent;
  395.          }
  396.         
  397.  // head points now again to the very first element
  398.  
  399.  return(head);
  400.  
  401. }
  402.  
  403. // ================ multipass ==========================================
  404.  
  405. ph_item* p_heap::multipass(ph_item* head)
  406. {
  407.           // now pass 1 (multi times) : left to right comparison link (successive pairs of root nodes)
  408.        ph_item* save=head;      
  409.        ph_item* help1,*help2;
  410.  
  411.        while(head->r_child!=nil)
  412.        { save=head;
  413.          help1=head;
  414.          help2=head->r_child;
  415.         
  416.          while (help2!=nil)      // there are 2 ore more elements left
  417.          { save=help1->r_child->r_child; // use of save as a helper
  418.            comparison_link(help1,help2);
  419.                 
  420.            if (save!=nil)       // first case comp _link
  421.              if (save->r_child!=nil)
  422.                 { // second case
  423.                   // now we have to more nodes to test
  424.                   help2=save->r_child;
  425.                   help1=save;
  426.                  }
  427.               else
  428.                  help2=nil;
  429.            else
  430.               { save=help1;     // last element in list
  431.                 help2=nil;
  432.                }
  433.          } // end while (help2!=nil)
  434.  
  435.  
  436.         if (head->parent!=nil)      // may be first element is child (comp link)
  437.                 head=head->parent;
  438.  
  439.     } // end while (repeat pass 1)
  440.  
  441.   return(head);
  442. }
  443.